package com.demo.java.OD451_500.OD470;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【寻找最优的路测线路(C&D卷-200分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146353497
 */
public class OdMain {
    // 最大信号质量值，用于二分查找的上限
    private static final int MAX_THRESHOLD = 65535;

    // BFS方法，判断是否存在一条路径，且路径上的信号质量都大于等于当前阈值
    public static boolean bfs(int R, int C, int threshold, int[][] matrix) {
        // 四个方向的移动：上、右、下、左
        int[] direction = {-1, 0, 1, 0, -1};

        // 用于记录访问过的节点
        int[][] visited = new int[R][C];
        visited[0][0] = 1; // 起点已经访问

        // 使用队列进行 BFS，队列中存放的是当前位置的行列编号
        Queue<Integer> q = new LinkedList<>();
        q.add(0 * MAX_THRESHOLD + 0); // 起点(0,0)

        while (!q.isEmpty()) {
            int current = q.poll();
            int x = current / MAX_THRESHOLD;
            int y = current % MAX_THRESHOLD;

            // 如果到达终点，返回true
            if (x == R - 1 && y == C - 1) {
                return true;
            }

            // 遍历四个方向
            for (int i = 0; i < 4; ++i) {
                int new_x = x + direction[i];
                int new_y = y + direction[i + 1];

                // 如果新位置合法，且信号质量满足阈值且未访问过
                if (new_x >= 0 && new_x < R && new_y >= 0 && new_y < C &&
                        visited[new_x][new_y] == 0 && matrix[new_x][new_y] >= threshold) {
                    visited[new_x][new_y] = 1; // 标记为已访问
                    q.add(new_x * MAX_THRESHOLD + new_y); // 将新位置加入队列
                }
            }
        }

        return false; // 如果没有路径符合条件
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取行数 R 和列数 C
        int R = scanner.nextInt();
        int C = scanner.nextInt();

        // 读取信号质量矩阵
        int[][] matrix = new int[R][C];
        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j) {
                matrix[i][j] = scanner.nextInt();
            }
        }

        // 二分查找信号质量的最小阈值
        int left = 0, right = MAX_THRESHOLD;

        while (left <= right) {
            int mid = left + (right - left) / 2; // 计算中间值

            // 使用 BFS 判断是否可以通过当前阈值
            if (bfs(R, C, mid, matrix)) {
                left = mid + 1; // 如果可以通过，尝试更大的阈值
            } else {
                right = mid - 1; // 如果不可以，通过小于当前阈值的路径
            }
        }

        // 输出结果，最大阈值减去1即为最终的信号质量阈值
        System.out.println(left - 1);
    }
}